
public class MyPriorityQueue<T> implements PriorityQueue<T> {

	private class Node{
		T elem;
		Node prev;
		Node next;
		
		Node(T elem, Node prev, Node next){
			this.elem=elem;
			this.prev=prev;
			this.next=next;
		}
		
		Node next(){
			return next;
		}
		
		Node add(T elem){
			Node cur;
			cur=this;
			while(cur.next!=null){
				cur=cur.next;
			}
			Node aux=new Node(elem,cur,null);
			cur.next=aux;
			return aux;
		}
	}
	
	private class PriorityList{
		int priority;
		Node list;
		Node last;
		PriorityList prevP;
		PriorityList nextP;
		int size=0;
		
		PriorityList(int priority, T elem, PriorityList prevP, PriorityList nextP){
			this.list.add(elem);
			this.priority=priority;
			this.nextP=nextP;
			this.prevP=prevP;
			this.last=list;
		}
		
		void add(T elem){
			list.add(elem);
			size++;
		}
	}
		
	private PriorityList pList;
	private PriorityList last;
	
	public MyPriorityQueue(){
	}
	
	@Override
	public T dequeue() {
		if(last==null){
			return null;
		}
		Node aux=last.last;
		aux.prev.next=aux.next;
		aux.next.prev=aux.prev;
		if(last.size==0){
			last.prevP.nextP=last.nextP;
			last.nextP.prevP=last.prevP;
		}
		return aux.elem;
	}

	@Override
	public void enqueue(T elem, int priority) {
		if(pList==null){
			pList=new PriorityList(priority,elem,null,null);
			last=pList;
			return;
		}
		
		PriorityList current=pList;
		
		while(current.nextP!=null){
			if(current.priority==priority){
				pList.add(elem);
				return;
			}
			else if(current.priority>priority){
				if(current.prevP==null){
					PriorityList aux=new PriorityList(priority,elem,current,null);
					aux.add(elem);
					last=aux;
					return;
				}
			}
			current=current.nextP;
		}
	}

	@Override
	public boolean isEmpty() {
		return pList==null;
	}

}
